package com.kuang.linkedlist;

/*      给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。*/


/**
 * @author kjx
 */
public class IsPalindrome {

    //不搞数组然后记录那种的了，直接上不要空间复杂度的
    //用了快慢双指针，以及上一题的反转数组；
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }

        ListNode fastNode = head, slowNode = head;
        //利用快指针比慢指针快1，当快指针到头的时候，慢指针就能在链表的中间后一位
        while (fastNode != null && fastNode.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        //如果快指针还存在，代表是一个奇数链表，那么慢指针下一个才是需要判断的点
        if (fastNode != null) {
            slowNode = slowNode.next;
        }
        //反转慢指针，也就是中间指针后面的链表
        slowNode = reverseList(slowNode);
        //然后头节点和慢指针后面的节点逐一对比即可
        while (slowNode != null) {
            if (head.val != slowNode.val) {
                return false;
            }
            head = head.next;
            slowNode = slowNode.next;
        }
        return true;
    }


    //反转链表，上一个题目的答案
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode curNode = head;    //cur是当前节点，一开始为head
        ListNode preNode = null;    //pre是当前节点前一个节点，头节点前面肯定是null啊
        while (curNode != null) {
            ListNode nextNode = curNode.next;   //呃呃呃，其实还是要用到三个指针，只是思路不同
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }
}
